/**
 * 双指针
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
let reverseKGroup = function (head, k) {
    if (k === 1 || head === null || head.next === null) return head

    let temp = head, headNext = head.next
    let m = 1
    // 翻转k个
    while (m < k && headNext !== null) {
        temp.next = headNext.next
        headNext.next = head

        head = headNext
        headNext = temp.next
        m++
    }
    console.log(m, k)

    // 如果不足k个，翻转回来
    if (m < k) return reverseKGroup(head, m)

    temp.next = reverseKGroup(headNext, k)

    return head
}

/**
 * 迭代翻转
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
let reverseKGroup2 = function (head, k) {
    if (k === 1 || head === null || head.next === null) return head
    
    let dummyNode = new ListNode(0)
    dummyNode.next = head

    let curPoint = dummyNode

    while (head) {
        let tail = curPoint

        for (let i = 0; i < k; i++) {
            tail = tail.next
            if (tail === null) return dummyNode.next
        }


        [head, tail] = reverseSub(head, tail)

        // 拼接到原链条，head翻转以后1后对应7，dummyNode和curPoint的1后也都对应7,5和4被删除，所以要拼接
        curPoint.next = head

        // 接着循环后续链
        head = tail.next
        curPoint = tail
    }

    return dummyNode.next
};

function reverseSub(head, tail) {
    // 比如head为1>4>5>7，k为3，tail为5>7
    let newHead = head
    let prev = tail.next

    // 直到prev指针指向第n*k位，他和tail的指针相同，tail会修改为prev的值
    // 第一次循环1的next指向7，head也被修改为1>7
    // 直到最后一次循环，prev的指针指向5，链为5>4>1>7，因为tail的指针一直是5，所以tail的链也被修改为5>4>1>7，引用地址相同，故相等
    while (prev !== tail) {
        let headNext = newHead.next
        newHead.next = prev

        prev = newHead
        newHead = headNext
    }

    // 一次翻转完成
    return [tail, head]
}


/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
let reverseKGroup3 = function (head, k) {
    if (k === 1 || head === null || head.next === null) return head

    let p = head

    for (let i = 0; i < k; i++) {
        if (p === null) {
            return head
        }
        p = p.next
    }

    let result = null
    let temp = head

    for (let i = 0; i < k; i++) {
        let newHead = temp.next
        temp.next = result

        result = temp
        temp = newHead
    }

    head.next = reverseKGroup(temp, k)

    return result
}


function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
}

let l1 = new ListNode(1)
l1.next = new ListNode(4)
l1.next.next = new ListNode(5)
l1.next.next.next = new ListNode(7)
l1.next.next.next.next = new ListNode(8)
